POI2008 Postering

POI2008 Postering

题目大意：

有n个矩形排成一排，现在希望用尽量少的矩型海报覆盖住它们。问最少需要几张海报。

题解：

首先我们可以知道，n张海报是一定可以满足条件的。大不了每一个矩形我都用一张海报。

但实际上，这肯定是不用这么多的。

当我们遇到这种情况时，我们不需要三张海报，而只需要两张。

总结一下我们发现，如果两个矩形高度相同，并且它们之间的矩形高度都比它们高，那么我们可以少花一个代价。

首先枚举两个相同高度的矩形，再用线段树求区间最小值，看是否满足条件。

这样题目就能够AC了，复杂度为$O(nlogn)$。

但实际上可以不这么写。我们维护一个单调栈，即可在$O(n)$的时间内解决该题。

Code:

线段树

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=250001;
int n,num[N],tmp[N];
struct Segment_Tree{
	struct node{
		int L,R,mi;
	}tree[N<<2];
	void pushup(int p){
		tree[p].mi=min(tree[p<<1].mi,tree[p<<1|1].mi);
	}
	void build(int L,int R,int p){
		tree[p].L=L,tree[p].R=R;
		if(L==R){
			tree[p].mi=num[L];
			return;
		}
		int mid=L+R>>1;
		build(L,mid,p<<1);
		build(mid+1,R,p<<1|1);
		pushup(p);
	}
	int query(int L,int R,int p){
		if(tree[p].L==L&&tree[p].R==R){
			return tree[p].mi;
		}
		int mid=tree[p].L+tree[p].R>>1;
		if(R<=mid)return query(L,R,p<<1);
		else if(L>mid)return query(L,R,p<<1|1);
		else return min(query(L,mid,p<<1),query(mid+1,R,p<<1|1));
	}
}T;
#include<vector>
vector<int>h[N];
int main(){
	Rd(n);
	for(int i=1,a;i<=n;i++){
		Rd(a),Rd(num[i]);
		tmp[i]=num[i];
	}
	sort(tmp+1,tmp+1+n);
	int len=unique(tmp+1,tmp+1+n)-tmp-1;
	for(int i=1;i<=n;i++)
		num[i]=lower_bound(tmp+1,tmp+1+len,num[i])-tmp;
	T.build(1,n,1);
	for(int i=1;i<=n;i++)
		h[num[i]].push_back(i);
	int ans=n;
	for(int i=1;i<=len;i++){
		for(int j=1;j<h[i].size();j++){
			int pre=h[i][j-1],cur=h[i][j];
			if(T.query(pre,cur,1)<i)continue;
			ans--;
		}
	}
	printf("%d\n",ans);
	return 0;
}

单调栈

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=250001;
int n,stk[N],top;
int main(){
	Rd(n);
	stk[top++]=0;
	int ans=n;
	for(int i=1,a,b;i<=n;i++){
		Rd(a),Rd(b);
		while(stk[top-1]>=b){
			if(stk[top-1]==b)ans--;
			top--;
		}
		stk[top++]=b;
	}
	printf("%d\n",ans);
	return 0;
}